import com.sun.source.tree.BreakTree;

import java.util.Iterator;

/**
 * 只有一个哨兵的 双向链表
 */
public class DoublyLikedListSentinel1 implements Iterable<Integer> {

    private Node sentinel = new Node(null, -1, null);


    private static class Node {
        int value;   //节点存储的值
        Node prev;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

    public DoublyLikedListSentinel1() {
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }

    /**
     * 添加到第一个元素
     */
    public void addFirst(int value) {
        Node a = sentinel;    //当只有哨兵时，a和b都是哨兵，也可以满足
        Node b = sentinel.next;
        Node insertedNode = new Node(a, value, b);
        a.next = insertedNode;
        b.prev = insertedNode;
    }

    /**
     * 添加到最后一个元素
     *
     * @return
     */
    public void addLast(int value) {
        Node a = sentinel.prev;
        Node b = sentinel;
        Node node = new Node(a, value, b);
        a.next = node;
        b.prev = node;
    }

    /**
     * 删除第一个元素
     */
    public void removeFirst() {
        Node a = sentinel;
        Node removedNode = sentinel.next;
        Node b = removedNode.next;
        if (removedNode == sentinel) {
            throw illegalIndex(0);
        }
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个元素
     */
    public void removeLast() {
        Node b = sentinel;
        Node removedNode = sentinel.prev;
        Node a = removedNode.prev;
        if (removedNode == sentinel) {
            throw illegalIndex(0);
        }
        a.next = b;
        b.prev = a;
    }

    /**
     * 根据值 找 节点
     */
    public Node findByValue(int value) {
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    /**
     * 根据值删除元素
     */
    public void removedByValue(int value) {
        Node removedNode = findByValue(value);
        if (removedNode == null) {
            return;
        }
        Node a = removedNode.prev;
        Node b = removedNode.next;
        a.next = b;
        b.prev = a;
    }

    private IllegalArgumentException illegalIndex(int index) {
        throw new IllegalArgumentException(String.format("index[%d]不合法%n", index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }


    public static void main(String[] args) {
        DoublyLikedListSentinel1 integers = new DoublyLikedListSentinel1();
        integers.addFirst(1);
        integers.addFirst(2);
        integers.addFirst(3);
        integers.forEach(System.out::println);
        integers.addLast(4);
        integers.addLast(5);
//        integers.forEach(System.out::println);
//        integers.removeFirst();
//        integers.removeFirst();
//        integers.removeFirst();
//        integers.forEach(System.out::println);
//        integers.removeLast();
//        integers.forEach(System.out::println);
        integers.removedByValue(4);
        integers.forEach(System.out::println);
    }
}
